#define DEBUG
#include <cstdio>
#define MODS 1000000007

using namespace std;

int main() {
#ifdef DEBUG
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif

  int t;
  scanf("%d", &t);
  for (int i=1; i<=t; i++) {
    long long l, r, a, ans=0;
    scanf("%lld %lld %lld", &l, &r, &a);
    for (long long i=l; i<=r; i++) {
      bool flag = i%a==0;
      int sum=0;
      for (long long j=i; j && !flag; j/=10) {
	if (j%10==a) {
	  flag=true;
	}
	sum +=j%10;
      }
      flag = flag || sum%a==0;

      ans = flag ? ans : (ans+i*i%MODS)%MODS;
#ifdef DEBUG
      if (flag) {
	printf("D:%lld ", i);
      }
#endif
    }

#ifdef DEBUG
    printf("\n");
#endif
    printf("%lld\n", ans);
  }

  fcloseall();
  return 0;
}
